1. Field of Invention
This invention especially relates to communications and computer systems; and more particularly, the invention relates to maintaining counters, such as in, but not limited to a packet switching system, and updating a secondary counter storage based on values of the counters and entries in an overflow buffer.
2. Description of the Background Art
The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). Note, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.
For example, in networking devices, it is important to maintain accurate packet and byte count counters for all traffic flowing through the device. Such counters are important for customers, for lab testing, and also for verification and debug purposes. Generally, counters must be maintained for a large number of items in a few different categories (e.g., individual routes the packets are taking, the adjacencies/next hops of the packets, etc.). It is not unusual for a network device to need to maintain counters on packets arriving at a rate of fifty million packets per second, and to have to support one million routes (e.g., one million different sets of packet and byte counters in the route category).
Many communications and computer systems keep large numbers of counters to indicate that certain events have occurred. Examples might include packets forwarded, bytes forwarded, overrate bytes, underrate bytes, etc. Externally-visible counters (e.g., those available to the system which are typically accumulated values from the counter bank counters maintained inside components, for example) typically must maintain total event counts that last for days, weeks, or even years. One frequent choice for packet processing applications is to use 64-bit externally-visible counters that are large enough to ensure that they will never wrap. These counters are typically implemented in RAM (usually DRAM or SDRAM). A corresponding counter is typically implemented in hardware and is usually much smaller than sixty-four bits, because typical special-purpose counter resources in the components are more expensive, and hence more limited than commodity system memory. In order to provide the external view of a large counter, the system software periodically reads each counter from the hardware device, adding the value read to an externally-visible counter that is stored in (cheap) system RAM.
The bit-width of the byte and packet counters in hardware are typically chosen such that, in the worse case, all counters can be visited before they overflow, assuming a particular rate at which the counters can be visited. The counter visitation rate is typically a system-dependent constant, and is typically limited by the total fraction of CPU time (or bus bandwidth in some cases) that is allocated to reading counters (and instead of performing other duties). For example, in a device with 100,000 counters, if the CPI performance may limit the rate that the counters can be read; while in other systems, the limitation might be bus bandwidth.
In implementations with the counter bank counters implemented on an application-specific integrated circuit (ASIC), it is not uncommon for the counter state to total many megabits of on-chip memory, occupying a non-trivial fraction of the total chip area. For example, one packet switch uses roughly 150,000 on-chip packet and byte counters with each counter having thirty-two bits of on-chip storage totaling 4.8 megabits of on-chip storage. Therefore, it is valuable if the on-chip storage required can be reduced while still ensuring that counters presented to the user do not wrap, and while not increasing CPU burden or bus bandwidth utilization required to read them periodically.
An issue in maintaining these counters is providing the necessary combination of storage space and bandwidth in a fashion that is cost effective, low in power, and low in pin count. Complicating the bandwidth issue is that, as the number of counters grows, the frequency at which software can reasonably read an individual counter lessens. The size and number of counters make storing the full counters directly on a packet switching chip expensive with today's technologies.
Previous solutions to the counter storage problem have addressed the cost of storage by moving the counters off-chip. This necessitates the use of expensive, high-bandwidth RAM (high-speed DDR or QDR SRAMs or DDR SDRAMS) that can keep up with the worst-case counter-update bandwidth requirements. If the packet arrival rate is fifty million packets per second, then the counter-update rate (for one type of counter) is fifty million counter updates per second in the worst case.
At a peak rate of fifty million counter updates per second, and using 128 bits to store both the byte and packet counters for one item, the bandwidth required for counter updates (which must read the old counter value and then write back an updated value) is approximately 12.8 gigabits per second. This data bandwidth could be achieved by a 64-bit wide Reduced Latency Dynamic Random Access Memory (RLDRAM) at 200 MHz, with appropriate attention to pipelining and bank conflicts. But this would only support one category of counter, and typical implementations have dozens of categories to maintain. As can be seen, the cost (in terms of board space, power budget, and dollars) of implementing this large a number of counters off-chip at the necessary throughput rate can be unacceptably high.
Some solutions to this problem have used FIFOs to compensate for reduced bandwidth and/or CPU activity (which can delay counter updates). These solutions have generally just used the FIFO as a buffer—the off-chip RAM is still designed for the worst-case bandwidth. (Typically, such FIFOs can hold no more than a few thousand entries, much smaller than the number of items.)
Another technique that has been used is to build two-level counters, where the least-significant bits (LSBs) and the most-significant bits (MSBs) are maintained separately. This can save bandwidth by only having to reference the MSBs when the LSBs overflow, instead of on every counter update. However, the storage required is not reduced.
Some aspects of the counter update problem are described in the article: Devarat Shah et al., Maintaining Statistics Counters in Router Line Cards, IEEE Micro, January-February 2002, pp. 76-81, which is hereby incorporated by reference. Shah et al. describe a theoretical approach, and a largest-counter-first counter management algorithm (LCF CMA) that selects a counter with the largest count to update to a secondary memory. This requires that some mechanism be employed to maintain counters in a sorted order or to quickly determine the largest counter. While this is a theoretically interesting approach, it is not generally practical to implement in current systems because of the cost of the sorting function. Shah et al. admit that their “LCF CMA is a complex algorithm that is hard to implement at a very high speed. It would be interesting to obtain a similar performance as LCF CMA with a less complex algorithm.” Id. At 80-81.